Very Large Scale Integrated (VLSI) chips include many electronic components (e.g., transistors, resistors, diodes, and the like) interconnected to form multiple circuit components (e.g., gates, cells, memory units, arithmetic units, controllers, decoders, and the like). The electronic and circuit components of the VLSI chip are jointly referred to as “components.”
A conventional VLSI circuit includes multiple layers of wiring (wiring layers) that interconnect the electronic and circuit components. For instance, VLSI chips are fabricated with metal or polysilicon wiring layers (collectively referred hereinafter as metal layers) that interconnect the electronic and circuit components. Common fabrication models use five or more metal layers. Wiring in each metal layer is laid out in a rectilinear or orthogonal manner so that each wire segment is parallel to either the X or Y axis.
Design engineers design VLSI chips by transforming the circuit description of the VLSI circuits into a geometric representation, referred to as layout using electronic design automation (EDA) applications. These applications provide sets of computer based tools for creating, editing, and analyzing the integrated circuit (IC) design layouts.
The layouts are created using geometric shapes representing different materials and devices of the ICs. For instance, EDA tools commonly use rectangular lines to represent wire segments interconnecting the IC components. The tools handle electronic and IC components as geometric objects of varying shapes and sizes. For sake of simplicity, geometric objects will henceforth be shown as rectangular blocks. A “circuit module” refers to the geometric representation of the electronic or IC components. Generally, the EDA applications designs typically handle circuit modules having pins on their sides, the pins making the necessary connections to the interconnect lines.
A net defines a collection of pins that need to be electrically connected. A list or subset of all the layout nets is referred to as a netlist. Thus, a netlist specifies a group of nets which, in turn, specifies the interconnections between the pins.
FIG. 1 is an illustrative example of a conventional IC layout 100. As shown, the layout includes five circuit modules 105, 110, 115, 120, and 125 with pins 130-160. Four interconnect lines 165-180 connect the modules to their pins. Additionally, three nets specify the interconnections between the pins. Pins 135, 145, and 160 define a three-pin net, while pins 130 and 155 and pins 140 and 150, respectively, and define a pair of two pin nets. As shown in FIG. 1, the circuit module (e.g., 105) can be provided with a plurality of pins of multiple nets.
The IC design process entails various operations. Some of the physical-design operations that EDA applications used to create IC layouts include: (1) circuit partitioning, which partitions a circuit if the circuit is too large for a single chip; (2) floor planning, that finds the alignment and relative orientation of the circuit modules; (3) placement, that determines more precisely the positions of the circuit modules; (4) routing, which completes the interconnects between the circuit modules; (5) compaction, which compresses the layout to decrease the total IC area; and (6) verification, which checks the layout to ensure that it meets design and functional requirements.
Routing is an essential operation of the physical design cycle. It is generally divided into two phases: global routing and detailed routing. For each net, global routing generates a “loose” route (also referred to as path or routing area) for the interconnect lines connecting the pins of the net. The “looseness” of the global route depends on a particular global router used. After creating the global routes, the detailed routing creates specific individual routing paths for each net.
Design automation of complex VLSI chips is often associated to a lengthy design turnaround time which, in turn, increases the time-to-market introduction. Two reasons for the large turnaround time problem include: slowness of the algorithms caused by large problem sizes (e.g., hundreds of millions of circuits and nets on a chip), and the large number of iterations between different algorithms requiring convergence to an acceptable level.
Current design tools are presently reaching the limit of their efficiency and speed as the number of circuit components such as transistors, diodes, capacitors, resistors, and the like, increase exponentially, and the complexity of their connectivity increases geometrically in term of the number of components.
A conventional approach towards improving the speed of VLSI design-automation algorithms is known as partitioning. Partitioning helps developers of the VLSI design automation tools to optimize the design parameters within each partition locally. Circuit netlists can be modeled as hypergraphs partitioned using various heuristics that are known to give good results, both in terms of runtime and quality of results.
In the geometric design of the VLSI chip, it is customary to represent circuit components such as terminals, connector corners and vias as a set of points in the X-Y plane. An example of the set of points is shown in FIG. 2A. Numeral 201 illustrates a terminal, and 200, a collection of points. The point set representation of geometric circuits allows the tool developer to concentrate on the underlying geometric relationship among different components rather than their synthetic connectivity relationship as determined by the circuit designer. An example of a net based on the points of FIG. 2A is referenced in FIG. 2B by numeral 210, consisting of 34 smaller rectangles, such as 215.
A major critical issue for any type of partitioning in the development of VLSI design automation algorithm is directed to the chip real estate. Since the number of components is very large and the space they occupy is always at a premium, it becomes necessary to minimize the total area of the partitions. Normally, there exists an upper bound on the number of such partitions that can be used to solve a particular problem since, as the number of partitions increases, the complexity of the algorithm(s) increases with it. The number of partitions may be determined by the designer on the basis of design constraints.
The conventional optical microlithography process in semiconductor fabrication, also known as the photolithography process, includes duplicating desired circuit patterns onto semiconductor wafers for an overall desired circuit performance. The desired circuit patterns can be represented as opaque, complete and semi-transparent regions on a template commonly referred to as a photomask. In an optical microlithography, patterns on the photomask template are projected onto a photoresist coated wafer by way of optical imaging through an exposure system.
The continuous advancement of VLSI chip manufacturing technology to meet Moore's law of shrinking device dimensions in a geometric progression has spurred the development of Resolution Enhancement Techniques (RET) and Optical Proximity Correction (OPC) methodologies in the optical microlithography. The latter is the method of choice for chip manufacturers for the foreseeable future due to its high volume yield in manufacturing and past history of success. However, the ever shrinking device dimensions combined with the desire to enhance circuit performance in the deep sub-wavelength domain require complex OPC methodologies to ensure the fidelity of mask patterns of the printed wafer.
In spite of significant advances in several forms of RET, the iterative Model-Based Optical Proximity Correction (MBOPC) has established itself as the method of choice for compensating the mask shapes for lithographic process effects. Conventional MBOPC tools include shapes on the mask design (henceforth referred to as the mask) typically defined as polygons. A pre-processing step is performed by dividing the edges of each mask shape into smaller line segments. At the heart of the MBOPC tool is a simulator that simulates the image intensity at a particular point, which is located at the center of each line segment. The segments are then moved back and forth, i.e., outwardly or inwardly from the feature interior from their original position on the mask shape at each iteration step of the MBOPC. The iteration stops as a result of the modification of the mask shapes when the image intensity at the pre-selected points matches a threshold intensity level within a tolerance limit.
While the quality of the OPC may improve as the number of segments increases, the efficiency of the MBOPC tool may decrease as the number of segments it simulates and iterates over in each iterative step increases. The number of segments, in turn, depends on the number of edges in each mask shape. Therefore, it is desirable that segments that are corrected are only those that are needed to obtain the desired lithographic quality.
While the model based OPC can be described as an optimization of mask shapes, another method known as source optimization is directed to optimizing the shape of the source pixels to improve the fidelity of the wafer shapes. The combined effect of the source and the mask optimization of the MBOPC is also known as the Source Mask Optimization (SMO).
SMO stems from the fact that light from different pixels of the source travels different distances to the wafer through the mask. The difference in traveled distances causes a phase difference in the beams of light emanating from different pixels. Differences in the phases determine how light beams interact at the wafer and mask levels. In case of constructive interferences, the light beams strengthen each other and strengthens the total effect of the light. In case of destructive interferences, the light beams weaken each other and weaken the total effect of the light. The object of SMO resides in determining the light pixels requiring to be turned on, such that the constructive interferences strengthen the effect of light where there is a need to have light on the wafer, and destructive interferences weaken the effect of light where no light is to be present thereon.
An example of a source after optimization is shown in FIG. 3 by way of numeral 300. A turned on pixel 301 is illustrated. The example illustrates only a limited number of pixels. A solution of source optimization with higher granularity of pixels is depicted in FIG. 3 by numeral 310.
Notwithstanding the above, it is still difficult and costly to construct a pixilated source as illustrated by, e.g. 301 and 310 (FIG. 3). An approximation of the source optimization is created by placing a filter in front of the source that approximates the ‘on pixels’. The requirement of such an approximation is that the solution pixels need to be contained within a rectilinear polygon.
The ever increasing cost of mask manufacturing and inspection and the ever increasing complexity of OPC and RET requires that the mask be correctly and accurately simulated for potential defects before the mask is manufactured. The area is generally known as Mask Manufacturability Verification or Optical Rule Checking (ORC), for which an accurate simulation is a primary concern of the ORC. This implies that the ORC simulation should not miss any real error on the mask. The cost of finding an error when the mask is actually manufactured and used for chip manufacturing is very high. Nevertheless, there are two other equally important objectives of a ORC tool. First, it needs to be done as rapidly as possible. The feedback from ORC is used for the development of OPC and RET. A fast feedback is useful to minimize the turn around time of the OPC and RET developments. Additionally, the number of few false errors should be minimized as much possible. A false error is defined as an error identified by ORC using the simulation tool, which does not happen on the wafer. Since a missed error is significantly more expensive than a false error, all the ORC tools are expected to err on the conservative side. However, since each error whether false or real needs to be checked manually, it is important that the number of false errors be minimized. If there are too many, the real errors may be missed by the manual inspection, requiring a significant amount of time to shift through all the false errors to find the real errors.
Current ORC methods tend to simulate the entire mask layout image with the most accurate geometry using conservative criteria and, further, and which have a tendency of increasing the runtime of the ORC along with the number of false errors.
The aforementioned methodology is illustrated in FIG. 4A. The input to the current art is one or more input mask layouts 401 created after application of one or more RET or OPC. Along with it, a target wafer image 400 is also provided as an input. In step 402, all the target and mask shapes are subdivided into segments. In step 403, a correspondence is established between each mask segment and one target shape. Next, in step 404, each mask segment is simulated using a calibrated resist and optical model. The simulated wafer segment is then compared against the corresponding target segment 405. If the simulated wafer segment is not contained within the tolerance of the corresponding target segment, it is reported as an error 407.
The proper functioning of a chip requires strong tolerance on the printability of a wafer image. Any deviation of such tolerance are classified as an error. This is demonstrated in FIG. 4B, wherein 451 and 452 are mask layout shapes, 451 are the main mask shapes, and 452 are examples of Sub-Resolution Assist Features (SRAF) which do not print themselves but help in printing the main mask shapes 451. The printed wafer image is shown as shaded shapes 455. Various kinds of errors are further illustrated in the image including:                461 depicts a “Necking Error”, where the wafer image width becomes smaller than a pre-determined value;        462 depicts a “Bridging Error”, where spacing between two wafer images becomes smaller than a predetermined value;        463 depicts an “Edge Placement Error”, where the wafer image edge is further away than the target edge of 451 by a predetermined value;        464 depicts an “Line End Shortening Error”, where the wafer image edge at a line end is further away than the target line-end edge of 451 by a predetermined value;        465 depicts an SRAF printing error, where a portion of the SRAF prints, even though SRAFs are not expected to be printed; and        466 depicts additional printing errors due to diffraction effects of lighting such as side lobe printing error.        
Errors are often shown as points or small rectangles on the mask, as shown in FIG. 4B, which illustrates two kinds of errors, depicted as point sets 411 and 412. Next, ORC localizes one type of errors within the cluster, bounding one group of errors within a bounding box, such as 415 (FIG. 4C) for group error 411. However, the bounding box does not show a very tight bound. Indeed, group of errors 411 includes the errors of group 412. This requires having a tighter bound on one set of errors that includes all the errors of the selected group, but which does not yet encounter too many other kinds of errors that can be simply described by a rectilinear polygon with a bounded number of edges.
In view of the aforementioned considerations, it is necessary to provide in industry a method for finding a rectilinear polygon containing a set of input points, the input points being either a set of points to be clustered as a netlist, or a set of pixilated source points, or a set of ORC errors. The rectilinear polygon needs to have a small area and at the same time it requires to be bounded by a limited number of edges. This requirement can also be defined by requiring that the rectilinear polygon be covered by a maximum k number of rectangles, where k is a user provided value.